package BinaryTree;

import java.util.ArrayList;
import java.util.List;

public class BinaryTree {
    static  class  TreeNode{
        public char val;//数据域
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用
        public TreeNode(char val){
            this.val =val;
        }
    }
    public TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right =E;
        C.left = F;
        C.right =G;
        E.right = H;
        return A;
    }
    //前序遍历
    public void PreOder(TreeNode root){
        if(root==null){
            return;
        }
        System.out.print(root.val+" ");
        PreOder(root.left);
        PreOder(root.right);
    }
    //oj题
    //给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    //遍历思路
   // List<Character> list = new ArrayList<>();
    /*public List<Character> preorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return  list;
    }*/
    //子问题
    public List<Character> preorderTraversal2(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
       List<Character> leftTree=preorderTraversal2(root.left);
       list.addAll(leftTree);
       List<Character> rightTree =preorderTraversal2(root.right);
       list.addAll(rightTree);
       return list;

    }
    //中序遍历
    public void InOder(TreeNode root){
        if(root==null){
            return;
        }
        InOder(root.left);
        System.out.print(root.val+" ");
        InOder(root.right);
    }

    //遍历思路
    /*public  List <Character> list =new ArrayList<>();
    public List<Character> inorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }*/
    //子问题
   /* public List<Character> inorderTraversal2(TreeNode root) {
        List<Character> list = new ArrayList<>();
        if(root==null){
            return list;
        }
        List<Character> leftTree = inorderTraversal(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Character> rightTree = inorderTraversal(root.right);
        list.addAll(rightTree);
        return list;
    }*/

    //后序遍历
    public void PostOder(TreeNode root){
        if(root==null){
            return;
        }
        PostOder(root.left);
        PostOder(root.right);
        System.out.print(root.val+" ");
    }
    //遍历思路
    public List<Character> list =new ArrayList<>();
    public List<Character> postorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return  list;
    }
    //子问题
    public List<Character> postorderTraversal2(TreeNode root) {
        List<Character> list =new ArrayList<>();
        List <Character> leftTree = postorderTraversal2(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = postorderTraversal2(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;

    }
}
